package com.suanfa.jiaoheng;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 第9课动态规划 {

    public static void main(String[] args) {
        List<Product> products = 创造商品();
        List<Integer> packageCapacities = 创造背包();
        动态规划背包(products,packageCapacities);
    }

    static class Product{
        // 商品名称
        String name;
        // 价值
        Integer value;
        // 重量
        Integer weight;

        public Product(String name, Integer value, Integer weight) {
            this.name = name;
            this.value = value;
            this.weight = weight;
        }
    }

    static List<Product> 创造商品(){
        List<Product> products = new ArrayList<>();
        products.add(new Product("音响",3000,4));
        products.add(new Product("笔记本",2000,3));
        products.add(new Product("吉他",1500,1));
        return products;
    }

    static List<Integer> 创造背包(){
        List<Integer> packageCapacities = new ArrayList<>();
        packageCapacities.add(1);
        packageCapacities.add(2);
        packageCapacities.add(3);
        packageCapacities.add(4);
        return packageCapacities;
    }

    static void 动态规划背包(List<Product> products,List<Integer> packageCapacities){
        Map<Integer,Integer> capacityAndPosMap = new HashMap<>();
        for(int i=0;i<packageCapacities.size();i++){
            capacityAndPosMap.put(packageCapacities.get(i),i);
        }

        int[][] maxValueTable = new int[products.size()][packageCapacities.size()];
        for(int i=0;i<products.size();i++){
            for(int j=0;j<packageCapacities.size();j++){
                // 当是第一件商品的时候，能装下这个商品就装，不能装，就保持0
                if(i==0){
                    if(products.get(i).weight<=packageCapacities.get(j)){
                        maxValueTable[i][j] =  products.get(i).value;
                    }
                    continue;
                }
                // 如果空间放不下本商品，直接填入此列对应上一行的数据
                if(products.get(i).weight > packageCapacities.get(j)){
                    maxValueTable[i][j] = maxValueTable[i-1][j];
                    continue;
                }
                // 判断本商品+剩余空间的价值和上一行中此列的值比较
                // 剩余空间
                int leftCapacity = packageCapacities.get(j)-products.get(i).weight;
                // 剩余空间的位置
                Integer pos = capacityAndPosMap.get(leftCapacity);
                int leftValue = 0;
                if(pos!=null){
                    // 这里需要i-1，因为假设每个商品只有一个，不能把当前商品添加两次
                    leftValue = maxValueTable[i-1][pos];
                }
                // 直到目前，剩余空间所能容纳的最大值
                // 本商品+剩余空间的价值和上一行中此列的值
                int newValue = products.get(i).value+leftValue;
                if(maxValueTable[i-1][j]<newValue){
                    maxValueTable[i][j] = newValue;
                }else{
                    maxValueTable[i][j] = maxValueTable[i-1][j];
                }
            }
        }
        System.out.println("下面打印整张表格");
        for(int i=0;i<products.size();i++){
            for(int j=0;j<packageCapacities.size();j++){
                System.out.printf("%-10s",maxValueTable[i][j]);
            }
            System.out.println("");
        }
        System.out.println("可以获取到的商品的最大价值为:"+maxValueTable[products.size()-1][packageCapacities.size()-1]);
    }
}
